home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 13085 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.2 KB

  1. Path: li.net!jeremy
  2. From: jeremy@newshost.li.net (Jeremy Markman)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Recursion
  5. Date: 4 Apr 1996 14:51:43 GMT
  6. Organization: LI Net (Long Island Network)
  7. Message-ID: <4k0nlv$hn6@linet06.li.net>
  8. References: <31624BC2.70D2@sooner.net>
  9. NNTP-Posting-Host: linet04.li.net
  10. X-Newsreader: TIN [version 1.2 PL2]
  11.  
  12. Eddie Bush (edwbush@sooner.net) wrote:
  13. : I am trying to construct a C function that will recursively convert
  14. : a string such as "1234" into it's integer equivelant (1234).
  15. : 2)the function should be called with a character pointer:
  16. :     Such as:   convert("1234");
  17. :   making the prototype look something like:
  18. :     int convert(char *p);
  19.  
  20. This is just off the top of my head:
  21.  
  22. int convert(char *string)
  23.  {
  24.   int value;
  25.   int len = strlen(string);
  26.  
  27.   if (string[0] == '\0')
  28.     return(0);
  29.   value = convert(string + 1);
  30.   if (len == 1)
  31.     value += string[0] - 1;
  32.   else
  33.    {
  34.     value /= 10 * (len - 1);
  35.     value += string[0] - '0';
  36.     value *= 10 * (len - 1);
  37.    }
  38.   return(value);
  39.  }
  40.  
  41. If you were to use a loop instead of recursion, the code may be slightly 
  42. smaller:
  43.  
  44. int convert(char *string)
  45.  {
  46.   int value = 0;
  47.   int i = 0;
  48.  
  49.   while (string[i] != '\0')
  50.    {
  51.     value = value * 10 + string[i] - '0';
  52.     i++;
  53.    }
  54.   return(value);
  55.  }
  56.  
  57. Theory time:
  58.  
  59. When parsing a string from left to right, you can convert the string to a 
  60. number without having to know how long the string is.  You just multiply 
  61. the current value by 10, then add the next character:
  62.  "1234"
  63.  0   * 10 + 1 = 1
  64.  1   * 10 + 2 = 12
  65.  12  * 10 + 3 = 123
  66.  123 * 10 + 4 = 1234
  67.  
  68. But when using recursion, you actually are parsing the string from right 
  69. to left, so you need to know how long the CURRENT string is.  What I've 
  70. done is divide the current value by some multiple of 10 so that the ones 
  71. digit becomes zero...Then, add the next digit, then multiply the new 
  72. value by that same multiple of 10, and you have the number...
  73. To wit:
  74.  
  75.   0 + 4                                                     =    4
  76.   4 / 10 * 1 = .4    |  .4   + 3 = 3.4    |  3.4   * 10 * 1 =   34
  77.  34 / 10 * 2 = .34   |  .34  + 2 = 2.34   |  2.34  * 10 * 2 =  234
  78. 234 / 10 * 3 = .234  |  .234 + 1 = 1.234  |  1.234 * 10 * 3 = 1234
  79.  
  80. Not bad for the top of my head...given more time, i'd think of a better 
  81. way, i'm sure...
  82.  
  83.